`
https://leetcode.cn/problems/edit-distance/
`

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
  const m = word1.length, n = word2.length
  const memo = Array.from({ length: m }, () => new Array(n).fill(-1))

  function dp(i, j) {
    // 其中有一个匹配完了，只需要把另一个全删了即可
    if (i === -1) return j + 1
    if (j === -1) return i + 1

    if (memo[i][j] !== -1) {
      return memo[i][j]
    }

    // 如果匹配上了就直接跳过
    if (word1[i] === word2[j]) {
      memo[i][j] = dp(i - 1, j - 1)
    } else {
      memo[i][j] = Math.min(
        // 插入
        // 直接在 word1[i] 后面插入一个和 word2[j] 一样的字符
        // 那么 word2[j] 就被匹配了，前移 j，继续跟 i 对比
        dp(i, j - 1) + 1,
        // 删除
        // 直接把 word1[i] 这个字符删掉
        // 前移 i，继续跟 j 对比
        dp(i - 1, j) + 1,
        // 替换
        // 直接把 word1[i] 替换成 word2[j]，这样它俩就匹配了
        // 同时前移 i，j 继续对比
        dp(i - 1, j - 1) + 1,
      )
    }

    return memo[i][j]
  }
  return dp(m - 1, n - 1)
};